from typing import *


class Solution:
    def minOperationsQueries(
        self, n: int, edges: List[List[int]], queries: List[List[int]]
    ) -> List[int]:
        nexts = [[] for _ in range(n)]  # 临边数组
        h = {}  # 边权重
        for u, v, w in edges:
            nexts[u].append(v)
            nexts[v].append(u)
            h[(u, v)] = w
            h[(v, u)] = w

        p = [-1] * n  # 直接上级数组
        depth = [0] * n
        ws = [[0] * 27 for _ in range(n)]

        def build_p(c, parent):
            p[c] = parent
            for next in nexts[c]:
                if next != parent:
                    depth[next] = depth[c] + 1
                    ws[next] = ws[c].copy()
                    ws[next][h[(c, next)]] += 1
                    build_p(next, c)

        build_p(0, -1)

        m = n.bit_length()

        pa = [[-1] * m for _ in range(n)]

        for i in range(n):
            pa[i][0] = p[i]

        for i in range(1, m):
            for j in range(n):
                if (p := pa[j][i - 1]) != -1:
                    pa[j][i] = pa[p][i - 1]

        def get_kth_ancestor(node, k):
            while k > 0 and node != -1:
                lb = k & -k
                node = pa[node][lb.bit_length() - 1]
                k ^= lb
            return node

        def get_lca(x: int, y: int) -> int:
            if depth[x] > depth[y]:
                x, y = y, x
            y = get_kth_ancestor(y, depth[y] - depth[x])
            if y == x:
                return x
            for i in range(len(pa[x]) - 1, -1, -1):
                px, py = pa[x][i], pa[y][i]
                if px != py:
                    x, y = px, py
            return pa[x][0]

        def f(a, b, ab):
            c = a.copy()
            for i in range(27):
                c[i] += b[i] - ab[i] * 2
            return sum(c) - max(c)

        ans = []
        for a, b in queries:
            ab = get_lca(a, b)
            ans.append(f(ws[a], ws[b], ws[ab]))
        return ans


s = Solution()
print(
    s.minOperationsQueries(
        n=7,
        edges=[[0, 1, 1], [1, 2, 1], [2, 3, 1], [3, 4, 2], [4, 5, 2], [5, 6, 2]],
        queries=[[0, 3], [3, 6], [2, 6], [0, 6]],
    )
)


# https://leetcode.cn/problems/kth-ancestor-of-a-tree-node/solutions/2305895/mo-ban-jiang-jie-shu-shang-bei-zeng-suan-v3rw/
